package edu.dali.algorithm.graph;

import java.util.Arrays;

public class Dijkstra {

    private WeightedGraph G;

    //原点s到某个顶点的相应的最短路径
    private int[] dis;
    //原点
    private int s;
    // 对应的那些顶点已经确定了最小值
    private boolean[] visited;

    public Dijkstra(WeightedGraph G, int s){
        this.G = G;
        //验证原点是合法的
        G.validateVertex(s);
        //开辟空间 有多少个顶点就有多个元素
        dis = new int[G.V()];
        //将每个点的距离赋值为无穷大
        Arrays.fill(dis , Integer.MAX_VALUE);
        //原点距离自己的距离为0
        dis[s] = 0;

        //开辟空间 默认为false
        visited = new boolean[G.V()];

        while(true) {
            // 当前找到的最小的dis值 默认是无穷大
            int curdis = Integer.MAX_VALUE;
            // 当前最小值的顶点， 默认是-1 （距离是正数）
            int cur = -1;
            //当前还没有确定最短路径中dis值最小的顶点
            for (int v = 0; v < G.V(); v++) {
                // visited 确认是否确认最短路径 当前结点的值 小于当前路径最小值
                if (!visited[v] && dis[v] < curdis) {
                    // 更新当前最小值
                    curdis = dis[v];
                    // 更新最小值的顶点
                    cur = v;
                }
            }
            //所有顶点已经遍历完 退出
            if (cur == -1) break;

            // 确认那些顶点已经找到
            visited[cur] = true;
            // 从cur顶点 遍历所有相邻顶点
            for (int w : G.adj(cur)) {
                //判断顶点是否访问过
                if (!visited[w]) {
                    // 判断原点到当前点的距离加上cur这条边的长度是否小于原点到w点更小
                    if (dis[cur]+G.getWeight(cur , w) < dis[w]) {
                        // 更新w点的最短距离
                        dis[w] = dis[cur]+G.getWeight(cur , w);
                    }
                }
            }
        }
    }

    //用户传来的顶点v是否有路径
    public boolean isConnectedTo(int v) {
        G.validateVertex(v);
        return visited[v];
    }

    // 原点s到顶点v 对应的最短路径的长度
    public int distTo(int v) {
        G.validateVertex(v);
        return dis[v];
    }

    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph("g.txt");
        Dijkstra dijkstra = new Dijkstra(g,0);
        for (int v = 0; v < g.V(); v++) {
            System.out.print(dijkstra.distTo(v) +" ");
        }
        System.out.println();
    }

}
